\subsubsection{Solución elegida}

Como los días en que llegan camiones vienen dados en la entrada como una lista desordenada de días, lo primero que hacemos es ordenar la lista(usamos merge sort).

A partir la lista ordenada obtenemos la cantidad de días distintos en que llegan camiones(diasCount). Luego creamos un array de diasCount elementos llamado camionesPorDia. Los elementos de este array son de tipo tupla<camiones:int, día:int> y cada elemento corresponde a un día con la correspondiente cantidad de camiones que llegan ese día. Para cargar camionesPorDia iteramos sobre la lista ordenada y creamos y le agregamos a camionesPorDia una tupla por cada vez que el elemento de la lista es distinto al anterior(cambio de día) o aumentamos en 1 la cantidad de camiones en la última tupla creada(aumentamos en 1 la cantidad de camiones para el día). 

Usando camionesPorDia obtenemos el día que maximiza el intervalo de camiones inspeccionados y la suma de los camiones en dicho intervalo. El algoritmo que realiza esto usa un ciclo y dos indices, startindex y endIndex, para recorrer camionesPorDia de forma que en cada iteración el intervalo de días entre los elementos startIndex y endIndex sea lo más grande posible y menor o igual a D(Nota: Para resumir, en varias oportunidades, usaremos "el elemento startIndex" o "el elemento endIndex" para referirnos a los elementos camionesPorDia[startIndex] y camionesPorDia[endindex] respectivamente). Además se usa un acumulador de camiones inicializado en 0, para almacenar la cantidad de camiones que hay en el intervalo considerado en cada iteración y otro para almacenar la cantidad maxima encontrada hasta el momento.

En cada iteración, startIndex aumenta en 1 por lo que el intervalo de días entre startIndex y endIndex disminuye. Entonces en cada iteración, se ejecuta un ciclo en el que mientras el intervalo de días sea menor a D, se aumenta endIndex y al mismo tiempo, se suma al acumulador la cantidad de camiones del elemento endIndex. Luego de ejecutarse este ciclo, se obtiene en el acumulador la cantidad de camiones en el intervalo.

Como en cada iteración se obtiene la cantidad de camiones que hay entre los elementos startIndex y endIndex, se compara esta cantidad con el valor máximo encontrado hasta el momento y si es mayor entonces se lo reemplaza. También se almacena el valor de startIndex en una variable, ya que el día del elemento startIndex es donde comienza el intervalo que hasta ahora tiene la mayor cantidad de camiones.

Por último, al final de la iteración se decrementa el valor del acumulador de camiones por la cantidad de camiones del elemento startIndex, ya que como en la próxima iteración el valor de startIndex se incrementará en 1, el acumulador seguirá teniendo la suma de camiones en el intervalo entre los elementos startIndex y endIndex.

Al final de cada iteración se chequea si endIndex es mayor o igual a la longitud de camionesPorDia y en ese caso se termina el ciclo. Esto se hace porque si endIndex llega hasta el último elemento, significa que todos los intervalos que se consideren en las próximas iteraciones(en caso de haber) estaran contenidos en el intervalo actual, ya que llegaran hasta este último elemento y startIndex aumentará de a 1 cada iteración. De modo que no tiene sentido considerarlos.


\subsubsection{Demostración}

La resolución del problema consta de partes claramente diferenciables: ordenamiento de la lista de días, creación del array de tuplas y obtención del día que maximiza la suma de camiones inspeccionados y dicha suma.

Lo que nos interesa estudíar es la última parte(que es la que resuelve el problema) y probar que es correcta. Para esto nos vamos a remitir al algoritmo descrito en el punto anterior. 
El algoritmo propuesto usa un ciclo que itera sobre camionesPorDia y utiliza dos índices para describir el intervalo de días considerado en cada iteración, startIndex y endIndex. 
El ciclo comienza ejecutando un ciclo interno que incrementa endIndex mientras endIndex sea menor a la longitud de camionesPorDia y el intervalo entre startIndex y endIndex sea menor a D:

\begin{quote}
\begin{verbatim}
while endIndex < |camionesPorDia| && camionesPorDia[endIndex].día - camionesPorDia[startIndex].día < D) then
   sumCamiones = sumCamiones + camionesPorDia[endIndex].camiones;
   endIndex = endIndex + 1;
endwhile
\end{verbatim}
\end{quote}

En la primera iteración del ciclo principal, startIndex y endIndex comienzan en 0 y cuando el ciclo interno termina, endIndex queda asignado a uno más el índice del último elemento de dicho intervalo y en sumCamiones queda acumulada la cantidad de camiones en el intervalo entre los elementos startIndex y endIndex :

\begin{quote}
sumCamiones = $\sum\limits_{i=startIndex}^{endIndex} camionesPorDia[i].camiones$
\end{quote}

Luego se compara el valor de sumCamiones con el de maxSumCamiones. Si sumCamiones es mayor a maxSumCamiones, entonces se asigna sumCamiones a maxSumCamiones y además se asigna a maxSumStartIndex el valor de startIndex:

\begin{quote}
\begin{verbatim}
if sumCamiones > maxSumCamiones then
   maxSumCamiones = sumCamiones;
   maxSumStartIndex = startIndex;
endif
\end{verbatim}
\end{quote}

En la primera iteración del ciclo principal, sumCamiones será mayor a 0 pues sera la suma de camiones en el primer intervalo considerado, calculado anteriormente. De modo que si hay al menos un día con camiones, entonces maxSumCamiones y maxSumStartIndex, serán asignados.

Antes de avanzar a la próxima iteración se resta a sumCamiones la cantidad de camiones del elemento startIndex y luego se aumenta startIndex en 1:

\begin{quote}
\begin{verbatim}
sumCamiones = sumCamiones - camionesPorDia[startIndex].camiones;
startIndex = startIndex + 1
\end{verbatim}
\end{quote}

De esta manera, en la próxima iteración el intervalo considerado comenzará siendo [startIndex+1, endIndex) y sumCamiones tendrá asignada la cantidad de camiones en dicho intervalo.

El ciclo principal se ejecutará mientras que startIndex sea menor a la longitud de camionesPorDia. De esta manera se iterará sobre todos los elementos de camionesPorDia. En las sucesivas iteraciones, se repetirán los pasos descriptos. 

Como en cada iteración, startIndex es 1 mayor que en la iteración anterior, la diferencia entre los días de los elementos startIndex y endIndex habra disminuido y por ende el ciclo interno incrementará el valor de endIndex mientras que el intervalo entre startIndex y endIndex sea menor a D. Luego el valor de sumCamiones sera nuevamente la sumatoria descripta anteriormente.

Como sumCamiones es en cada iteración la suma de camiones entre los días de los elementos startIndex y endIndex y en cada iteración se compara con el valor de maxSumCamiones, luego al terminar el ciclo, en maxSumCamiones quedará almacenado el valor máximo de sumCamiones y por consiguiente el startIndex correspondiente a dicho valor en maxSumStartIndex.

Antes de terminar el ciclo ejecuta la siguiente sentencia:

\begin{quote}
\begin{verbatim}
if endIndex >= |camionesPorDia| then
   startIndex = |camionesPorDia|;
endif
\end{verbatim}
\end{quote}

Usamos esta sentencia para obviar procesar los intervalos incluidos en el primer intervalo que termine en endIndex, ya que dichos intervalos estarán contenidos en este.

Como los intervalos están contenidos en el intervalo más grande, entonces la cantidad de camiones en esos intervalos siempre sera menor al intervalo que los contiene y por ende no tiene sentido considerarlos.

Para ejemplificar esto, se puede tener en cuenta el caso en que D es mayor a la longitud de camionesPorDia y entonces el ciclo principal solo se ejecutará una vez, ya que startIndex y endIndex abarcarán todos los elementos en camionesPorDia, y sino se tuviese esta sentencia, entonces se considerarían todos los subintervalos de este, lo cual aunque no rompería el algoritmo, atentaría con la complejidad buscada.


